﻿#pragma once
#include<string>
#include<vector>
#include<iostream>
using namespace std;

namespace wzy {
	namespace hash_bucket
	{
		template<class T>
		struct HashNode
		{
			T _data;
			HashNode<T>* _next;
			HashNode(const T& data)
				:_data(data)
				, _next(nullptr)
			{}
		};

		// K 为 T 中key的类型
		// T 可能是键值对，也可能是K
		// KeyOfT: 从T中提取key
		// Hash将key转化为整形，因为哈希函数使用除留余数法
		template<class K, class T, class KeyOfT, class Hash>
		class HashTable
		{

			typedef HashNode<T> Node;
		public:
			HashTable()
			{
				_tables.resize(10, nullptr);
			}

			// 哈希桶的销毁
			~HashTable()
			{
				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while(cur)
					{
						Node* next = cur->_next;
						delete cur;

						cur = next;
					}
					_tables[i] = nullptr;
				}
			}

			// 插入值为data的元素，如果data存在则不插入
			bool Insert(const T& data)
			{
				KeyOfT kot;
				Hash hs;

				//插入的数据已经存在
				if(Find(kot(data)))
					return false;

				//负载因子为1时扩容
				if (_n == _tables.size())
				{
					vector<Node*> newHT(_tables.size()*2,nullptr);
					for (size_t i = 0; i < _tables.size(); i++)
					{
						Node* cur = _tables[i];
						while (cur)
						{
							Node* next = cur->_next;
							//头插到新表里
							size_t hashi = hs(kot(cur->_data)) % newHT.size();
							cur->_next = newHT[hashi];
							newHT[hashi] = cur;

							cur = next;
						}
						_tables[i] = nullptr;
					}

					_tables.swap(newHT);
				}

				size_t hashi = hs(kot(data)) % _tables.size();
				//头插
				Node* newnode = new Node(data);
				newnode->_next = _tables[hashi];
				_tables[hashi] = newnode;
				++_n;
				return true;
			}

			// 在哈希桶中查找值为key的元素，存在返回true否则返回false﻿
			bool Find(const K& key)
			{
				Hash hs;
				size_t hashi = hs(key) % _tables.size();

				//在对应的桶里查找数据
				Node* cur = _tables[hashi];
				KeyOfT kot;
				while (cur)
				{
					if (kot(cur->_data) == key)
						return true;

					cur = cur->_next;
				}

				return false;
			}

			// 哈希桶中删除key的元素，删除成功返回true，否则返回false
			bool Erase(const K& key)
			{
				Hash hs;
				KeyOfT kot;
				size_t hashi = hs(key) % _tables.size();
				Node* prev = nullptr;
				Node* cur = _tables[hashi];
				while (cur)
				{
					if (kot(cur->_data) == key)
					{
						//删除结点为头结点
						if (prev == nullptr)
						{
							_tables[hashi] = cur->_next;
						}
						//删除结点为中间结点
						else
						{
							prev->_next = cur->_next;
						}

						delete cur;
						--_n;
						return true;
					}
					else
					{
						prev = cur;
						cur = cur->_next;
					}
				}
				return false;
			}

		private:
			vector<Node*> _tables;  // 指针数组
			size_t _n = 0;			// 表中存储数据个数
		};

	}

	template<class K>
	struct Hash
	{
		size_t operator()(const K& key)
		{
			return key;
		}
	};

	template<>
	struct Hash<string>
	{
		size_t operator()(const string& s)
		{
			size_t hashi = 0;
			for (auto e : s)
			{
				hashi *= 31;
				hashi += e;
			}
			return hashi;
		}
	};

	template<class K,class T>
	struct KeyOfT
	{
		const K& operator()(const T& data)
		{
			return data;
		}
	};

	template<class K, class T>
	struct SKeyOfT
	{
		const K& operator()(const T& data)
		{
			return data.first;
		}
	};


	void test_int()
	{
		hash_bucket::HashTable<int, const int, KeyOfT<int,int>, Hash<int>> HT;
		int a[] = { 12,14,54,17,42,52,18 };
		for (auto e : a)
		{
			HT.Insert(e);
		}

		cout << HT.Find(42) << endl;
		HT.Insert(33);
		HT.Insert(13);
		HT.Insert(53);
		HT.Insert(83);
		cout << HT.Find(42) << endl;
		HT.Erase(13);
		HT.Erase(53);
		HT.Erase(12);
	}

	void test_string()
	{
		hash_bucket::HashTable<string, pair<string, string>, SKeyOfT<string, pair<string, string>>, Hash<string>> HT;
		HT.Insert({ "left","左边" });
		HT.Insert({ "right","右边" });
		HT.Insert({ "insert","插入" });
		HT.Insert({ "delete","删除"});

	}
}